Elsewhere we have introduced the sequential ordering problem with precedence relationships, SOP. In this paper we extent the problem to the case where time windows are considered. The problem has a broad range of applications, mainly, in production planning for manufacturing systems. Given a set of nodes. a weight associated with each node and a weight associated with each pair of nodes that can be sequenced consecutively. the SOP consists of finding a Hamiltonian path, such that release and due dates for each node and precedence relationships among the nodes are satisfied and a linear function is minimized. We present a tight formulation of the problem. and the framework for a cut generation LP based procedure for obtaining the optimal solution.
By: L. F. Escudero, A. Sciomachen
Published in: RC16820 in 1991
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .